package mid.两个维度权衡问题;

import java.util.Arrays;

/**
 * @author zhengTao
 * @version 1.0
 * @description: 分发糖果
 * @date 2022/11/21 10:43
 */
public class Demo135 {

    public int candy(int[] ratings) {
        //定义每个位置小孩得到的糖果数
        int[] dp=new int[ratings.length];
        Arrays.fill(dp,1);
        //从左往右遍历，右边的评分大于左边的，则糖果数字加一,从1位置开始遍历
        for (int i = 1; i < ratings.length; i++) {
            if(ratings[i]>ratings[i-1]){
                dp[i]=dp[i-1]+1;
            }
        }
        //再从右往左遍历，如果左边评分的大于右边，
        // 则左边的糖果有两种情况(已经大于右边的糖果数，则不变，小于或者等于，则是右边的糖果数加)，
        // 从倒数第二个开始遍历
        for (int i = ratings.length - 2; i >= 0; i--) {
            if(ratings[i]>ratings[i+1]){
                dp[i]=Math.max(dp[i],dp[i+1]+1);
            }
        }

       return Arrays.stream(dp).sum();
    }
}
